package cn.itcast.algorithm.exercise;

import java.util.Scanner;

/**
 * 动态规划 最大子数组
 * create by zhangtian105 on 2022/5/24
 */
public class ExerciseAB36 {
    public static void main(String[] args) {
        // 初始化数据
        Scanner scanner = new Scanner(System.in) ;
        int arrLength = scanner.nextInt() ;

        if (arrLength <= 0) {
            return;
        }

        int[] arr = new int[arrLength] ;

        for (int i = 0; i < arrLength; i++) {
            arr[i] = scanner.nextInt() ;
        }

        int res = Integer.MIN_VALUE ;

        if (arrLength == 1) {
            res = arr[0] ;
            System.out.println(res);
            return;
        }

        int[] dp = new int[arrLength] ;
        dp[0] = arr[0] ;
        for (int i = 1; i < arrLength; i++) {
            dp[i] = Math.max(dp[i-1]+arr[i], arr[i]) ;
        }

        for (int i = 0; i < arrLength; i++) {
            if (dp[i] > res) {
                res = dp[i] ;
            }
        }

        System.out.println(res);
    }
}
